package leetCode.solution;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
 * 
 * @author jerry
 * @ClassName: Solution199
 * @Description:TODO(描述这个类的作用)
 * @date 2022年12月15日 下午2:45:20
 */
public class Solution199 {

	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode() {
		}

		TreeNode(int val) {
			this.val = val;
		}

		TreeNode(int val, TreeNode left, TreeNode right) {
			this.val = val;
			this.left = left;
			this.right = right;
		}
	}

	public List<Integer> rightSideView(TreeNode root) {
		List<Integer> result = new ArrayList<Integer>();
		if(root==null) {
			return result;
		}

		LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
		queue.offerLast(root);
		while(!queue.isEmpty()) {
			int n = queue.size();
			for(int i = 0;i<n;i++) {
				TreeNode node = queue.pollLast();
				if(node.left!=null) {
					queue.offerFirst(node.left);
				}
				if(node.right!=null) {
					queue.offerFirst(node.right);
				}
				if(i==n-1) {
					result.add(node.val);
				}
			}
		}
		return result;
	}

}
